\subsection{Notation}
The interpretation of a function symbol \( f \) in a model \( \mathcal M \) is denoted by \( f^{\mathcal M} \), and similarly the interpretation of a relation symbol \( R \) in \( \mathcal M \) is denoted by \( R^{\mathcal M} \).
If \( \mathcal M \) is an \( \mathcal L \)-structure, and \( A \subseteq \mathcal M \) is a subset, we will write \( \mathcal L_A \) for the language obtained by adding a new constant symbol \( a \) to the signature of \( \mathcal L \) for each element \( a \) of \( A \).
Then \( \mathcal M \) is naturally an \( \mathcal L_A \)-structure by interpreting the constants in the obvious way.
We will allow for the empty set to be an \( \mathcal L \)-structure.

\subsection{Homomorphisms and substructures}
\begin{definition}
    Let \( \mathcal M \) and \( \mathcal N \) be \( \mathcal L \)-structures.
    An \emph{\( \mathcal L \)-homomorphism} is a map \( \eta : \mathcal M \to \mathcal N \) that preserves the interpretations of the symbols in the language: given \( \vb a = (a_1, \dots, a_n) \in \mathcal M^n \),
    \begin{enumerate}
        \item for all function symbols \( f \) of arity \( n \), we have that
        \[ \eta(f^{\mathcal M}(\vb a)) = f^{\mathcal N}(\eta(\vb a)) \]
        \item for all relation symbols \( r \) of arity \( n \), we have that
        \[ \vb a \in R^{\mathcal M} \iff \eta(\vb a) \in R^{\mathcal N} \]
    \end{enumerate}
    An injective \( \mathcal L \)-homomorphism is called an \emph{\( \mathcal L \)-embedding}.
    An invertible \( \mathcal L \)-homomorphism is called an \emph{\( \mathcal L \)-isomorphism}.
\end{definition}
\begin{definition}
    If \( \mathcal M \subseteq \mathcal N \) and the inclusion map is an \( \mathcal L \)-homomorphism, we say that \( \mathcal M \) is a \emph{substructure} of \( \mathcal N \), and that \( \mathcal N \) is an \emph{extension} of \( \mathcal M \).
    We will typically use the notation \( \mathcal M \subseteq \mathcal N \) to indicate that \( \mathcal M \) is a substructure of \( \mathcal N \) when both are \( \mathcal L \)-structures, not just that it is a subset.
\end{definition}
\begin{example}
    \begin{enumerate}
        \item Let \( \mathcal L \) be the language of groups.
        Then \( (\mathbb N, +, 0) \) is a substructure of \( (\mathbb Z, +, 0) \), but it is not a subgroup.
        \item If \( \mathcal M \) is an \( \mathcal L \)-structure, \( X \) is the domain of a substructure of \( \mathcal M \) if and only if it is closed under the interpretations of all function symbols.
        The forward implication is clear.
        If \( f \) is a function symbol of arity \( n \) and \( X \) is closed under \( f^{\mathcal M} \), \( \eval{f^{\mathcal M}}_{X^n} \) is a function \( X^n \to X \) interpreting \( f \) on the domain \( X \), as required.
        In particular, any substructure should also contain all of the constants in the language.
        \item The substructure \emph{generated by} a subset \( X \subseteq \mathcal M \) is given by the smallest set that contains \( X \) and is closed under the interpretations of all function symbols in \( \mathcal M \).
        This is denoted \( \langle X \rangle_{\mathcal M} \), and one can check that for infinite \( \mathcal L \) (but not necessarily infinite signature),
        \[ \abs{\langle X \rangle_{\mathcal M}} \leq \abs{X} + \abs{\mathcal L} \]
        We prove this by iteratively closing up \( X \) by applying interpretations of function symbols to elements of \( X \), and then taking the union of the resulting sets.
        At each stage, for each function symbol \( f \) of arity \( n \), we add at most \( \abs{X}^n \leq \abs{X} \cdot \aleph_0 \) new elements.
        So in a single stage, we add at most \( \abs{X} \cdot \aleph_0 \cdot \abs{\mathcal L} = \abs{X} \cdot \abs{\mathcal L} \) new elements to \( X \).
        Repeating this \( \omega \) times, the final set has size at most
        \begin{align*}
            \abs{X} + \abs{X} \cdot \abs{\mathcal L} + \abs{X} \cdot \abs{\mathcal L}^2 + \cdots &= \abs{X} (1 + \abs{\mathcal L} + \abs{\mathcal L}^2 + \cdots) \\
            &\leq \abs{X} (\abs{\mathcal L} + \abs{\mathcal L} + \abs{\mathcal L} + \cdots) \\
            &= \abs{X} \cdot \abs{\mathcal L} \cdot \aleph_0 \\
            &= \abs{X} \cdot \abs{\mathcal L}
        \end{align*}
        We say that \( \mathcal M \) is \emph{finitely generated} if there exists a finite subset \( X \subseteq \mathcal M \) such that \( \mathcal M = \langle X \rangle_{\mathcal M} \).
        \item Consider
        \[ (\mathbb R, \cdot, -1) \vDash \neg \exists x.\, (x^2 = -1) \]
        But it has an extension \( (\mathbb C, \cdot, -1) \) that does not model this sentence.
    \end{enumerate}
\end{example}
\begin{proposition}
    Let \( \varphi(\vb x) \) be a quantifier-free \( \mathcal L \)-formula with \( n \) free variables.
    Let \( \mathcal M \) be an \( \mathcal L \)-structure, and let \( \vb a \) be an \( n \)-tuple in \( \mathcal M \).
    Then for every extension \( \mathcal N \) of \( \mathcal M \),
    \[ \mathcal M \vDash \varphi(\vb a) \iff \mathcal N \vDash \varphi(\vb a) \]
\end{proposition}
\begin{proof}
    We proceed by induction on the structure of formulae.
    First, we show that if \( t(\vb x) \) is a term with \( k \) free variables, then
    \[ t^{\mathcal M}(\vb b) = t^{\mathcal N}(\vb b) \]
    for all \( \vb b \in \mathcal M^k \).
    It is clearly the case if \( t = x_i \) is a variable, as both structures interpret \( t(\vb b) \) as \( b_i \).
    Suppose \( t \) is a term of the form \( t = f(q_1, \dots, q_\ell) \) for \( f \) a function symbol of arity \( \ell \) and the \( q_i \) are terms.
    By the inductive hypothesis we have
    \[ q_i^{\mathcal M}(\vb b) = q_i^{\mathcal N}(\vb b) \]
    Therefore,
    \begin{align*}
        t^{\mathcal M}(\vb b) &= f^{\mathcal M}(q_1^{\mathcal M}(\vb b), \dots, q_\ell^{\mathcal M}(\vb b)) \\
        &= f^{\mathcal N}(q_1^{\mathcal M}(\vb b), \dots, q_\ell^{\mathcal M}(\vb b)) \\
        &= f^{\mathcal N}(q_1^{\mathcal N}(\vb b), \dots, q_\ell^{\mathcal N}(\vb b)) \\
        &= t^{\mathcal N}(\vb b)
    \end{align*}
    Thus terms are interpreted the same way in both models.
    For terms \( t_1, t_2 \) with the same free variables \( \vb x \), then for any choice of \( \vb a \),
    \begin{align*}
        \mathcal M \vDash (t_1(\vb x) = t_2(\vb x)) &\iff t_1^{\mathcal M}(\vb a) = t_2^{\mathcal M}(\vb a) \\
        &\iff t_1^{\mathcal N}(\vb a) = t_2^{\mathcal M}(\vb b) \\
        &\iff \mathcal N \vDash (t_1(\vb x) = t_2(\vb x))
    \end{align*}
    Let \( R \) be a relation symbol of arity \( n \), and let \( t_1, \dots, t_n \) be terms with the same free variables \( \vb x \).
    \begin{align*}
        \mathcal M \vDash R(t_1(\vb x), \dots, t_n(\vb x)) &\iff (t_1^{\mathcal M}(\vb a), \dots, t_n^{\mathcal M}(\vb a)) \in R^{\mathcal M} \\
        &\iff (t_1^{\mathcal M}(\vb a), \dots, t_n^{\mathcal M}(\vb a)) \in R^{\mathcal N} \\
        &\iff (t_1^{\mathcal N}(\vb a), \dots, t_n^{\mathcal N}(\vb a)) \in R^{\mathcal N} \\
        &\iff \mathcal N \vDash R(t_1(\vb x), \dots, t_n(\vb x))
    \end{align*}
    So the result holds for all atomic formulae.
    For connectives, note that
    \begin{align*}
        \mathcal M \vDash \neg \varphi &\iff \mathcal M \nvDash \varphi \\
        &\iff \mathcal N \nvDash \varphi \\
        &\iff \mathcal N \vDash \neg \varphi
    \end{align*}
    and
    \begin{align*}
        \mathcal M \vDash \varphi \wedge \psi &\iff (\mathcal M \vDash \varphi) \wedge (\mathcal M \vDash \psi) \\
        &\iff (\mathcal N \vDash \varphi) \wedge (\mathcal N \vDash \psi) \\
        &\iff \mathcal N \vDash \varphi \wedge \psi
    \end{align*}
    As quantifier-free formulae can be built out of atomic formulae, negation, and conjunction, we have completed the proof.
\end{proof}

\subsection{Elementary equivalence}
\begin{definition}
    Structures \( \mathcal M, \mathcal N \) are called \emph{elementarily equivalent} if for every \( \mathcal L \)-sentence,
    \[ \mathcal M \vDash \varphi \iff \mathcal N \vDash \varphi \]
    A map \( f : \mathcal M \to \mathcal N \) is an \emph{elementary embedding} if it is injective, and for all \( \mathcal L \)-formulae \( \varphi(x_1, \dots, x_n) \) and elements \( m_1, \dots, m_n \in \mathcal M \), we have
    \[ \mathcal M \vDash \varphi(m_1, \dots, m_n) \iff \mathcal N \vDash \varphi(f(m_1), \dots, f(m_n)) \]
\end{definition}
If there is an elementary embedding between two structures, they are elementarily equivalent.
If \( \mathcal M \) and \( \mathcal N \) are elementarily equivalent, we write \( \mathcal M \equiv \mathcal N \).
\begin{remark}
    If \( \mathcal M \) and \( \mathcal N \) are \( \mathcal L \)-structures, and \( \vb m \in \mathcal M, \vb n \in \mathcal N \) are ordered tuples of the same length \( k \), then by
    \[ (\mathcal M, \vb m) \equiv (\mathcal N, \vb n) \]
    we view \( (\mathcal M, \vb m) \) and \( (\mathcal N, \vb n) \) as structures over \( \mathcal L \) with \( k \) additional constants, interpreting these new constants as the elements of \( \vb m \) and \( \vb n \) respectively.
\end{remark}
\begin{proposition}
    If \( \mathcal M \cong \mathcal N \), then \( \mathcal M \equiv \mathcal N \).
\end{proposition}
This can be easily shown by induction.
The converse is generally not true, for example if the structures are infinite.
\begin{definition}
    A substructure \( \mathcal M \subseteq \mathcal N \) is an \emph{elementary substructure} if the inclusion map is an elementary embedding.
    In this case, we also say that \( \mathcal N \) is an \emph{elementary extension} of \( \mathcal M \).
    We write \( \mathcal M \preceq \mathcal N \).
\end{definition}

\subsection{Categorical and complete theories}
Recall that a theory \( \mathcal T \) is \emph{complete} if either \( \mathcal T \vdash \varphi \) or \( \mathcal T \vdash \neg\varphi \) for all sentences \( \varphi \).
Then any two models of a complete theory are elementarily equivalent, but they may have different cardinalities.
\begin{definition}
    A theory \( \mathcal T \) is \emph{model-complete} if every embedding between models of \( \mathcal T \) is elementary.
\end{definition}
\begin{definition}
    Let \( \kappa \) be an infinite cardinal.
    A theory \( \mathcal T \) is \emph{\( \kappa \)-categorical} if all models of \( \mathcal T \) of cardinality \( \kappa \) are isomorphic.
\end{definition}
It turns out that if theory on a countable language is categorical for some uncountable cardinal, then it is categorical for all infinite cardinals.
\begin{proposition}[Vaught's test]
    Let \( \mathcal T \) be a consistent \( \mathcal L \)-theory that has no finite models.
    If \( \mathcal T \) is \( \kappa \)-categorical for some infinite \( \kappa \geq \abs{\mathcal L} \), then \( \mathcal T \) is complete.
\end{proposition}
\begin{proof}
    Suppose there is some \( \varphi \) such that \( \mathcal T \nvdash \varphi \) and \( \mathcal T \nvdash \neg \varphi \).
    Then \( \mathcal T \cup \qty{\varphi} \) and \( \mathcal T \cup \qty{\neg\varphi} \) are consistent theories, so have models.
    As \( \mathcal T \) has no finite models, these two models are infinite.
    In fact, by the L\"owenheim--Skolem theorem, the models can be forced to have size \( \kappa \).
    But these models are in particular models of \( \mathcal T \), so they must be isomorphic.
    Since they are isomorphic, they are elementarily equivalent.
    But the models disagree on the truth value of \( \varphi \), giving a contradiction.
\end{proof}
\begin{example}
    \begin{enumerate}
        \item Any two countable dense linear orders are isomorphic, so the theory of dense linear orders without endpoints is \( \aleph_0 \)-categorical.
        Thus, by Vaught's test, the theory \( \mathsf{DLO} \) of dense linear orders without endpoints is complete.
        \item Let \( F \) be a field.
        The theory of infinite (not infinite-dimensional) \( F \)-vector spaces is \( \kappa \)-categorical for \( \kappa > \abs{F} \). % (exercise)
        Hence, the theory is complete.
    \end{enumerate}
\end{example}

\subsection{Tarski--Vaught test}
\begin{proposition}
    Let \( \mathcal N \) be an \( \mathcal L \)-structure, and let \( M \subseteq \mathcal N \).
    Then \( M \) is the domain of an elementary substructure if and only if for any formula \( \varphi(x, \vb t) \) and tuple \( \vb m \in M \), if there exists a witness \( n \in \mathcal N \) such that \( \mathcal N \vDash \varphi(n, \vb m) \), then there is a witness \( \hat n \in M \) such that \( \mathcal N \vDash \varphi(\hat n, \vb m) \).
\end{proposition}
\begin{proof}
    If \( M \) is the domain of an elementary substructure \( \mathcal M \), then \( \mathcal N \vDash \exists x.\, \varphi(x, \vb m) \) implies that \( \mathcal M \vDash \exists x.\, \varphi(x, \vb m) \).
    Thus \( \mathcal M \vDash \varphi(\hat m, \vb m) \) for some \( \hat m \in \mathcal M \).
    But then \( \mathcal N \vDash \varphi(\hat m, \vb m) \), as required.

    For the other implication, if \( M \subseteq \mathcal N \) has the stated property, we first show that \( M \) is closed under the interpretation of function symbols.
    Consider the formulae \( \varphi_f(x, \vb t) = (x = f(\vb t)) \) for each function symbol \( f \) in \( \mathcal L \).
    Then for any \( \vb m \in M \), there exists \( n \in \mathcal N \) such that \( \mathcal N \vDash n = f(\vb m) \), but then by hypothesis, there exists \( \hat m \in M \) such that \( \mathcal N \vDash \hat m = f(\vb m) \).
    Thus \( f(\vb m) = \hat m \in M \).
    Interpreting relation symbols on \( M \) in the obvious way, we turn \( M \) into an \( \mathcal L \)-structure \( \mathcal M \), which is clearly a substructure of \( \mathcal N \).

    It now remains to show that the substructure \( \mathcal M \) of \( \mathcal N \) is elementary.
    This follows from induction over the number of quantifiers in formulae, noting that the truth values of quantifier-free formulae are always preserved under any extension.
\end{proof}

\subsection{Universal theories and the method of diagrams}
\begin{definition}
    A formula \( \varphi \) is \emph{universal} if it is of the form \( \forall \vb x.\, \psi(\vb x, \vb y) \) where \( \psi \) is quantifier-free.
    A theory is \emph{universal} if all its axioms are universal sentences.
\end{definition}
\begin{definition}
    Let \( \mathcal N \) be an \( \mathcal L \)-structure.
    We define the \emph{diagram} of \( \mathcal N \) to be the set
    \[ \operatorname{Diag} \mathcal N = \qty{\varphi(n_1, \dots n_k) \mid \varphi \text{ is a quantifier-free } \mathcal L_{\mathcal N} \text{-formula}, \mathcal N \vDash \varphi(n_1, \dots, n_k)} \]
    The \emph{elementary diagram} of \( \mathcal N \) is
    \[ \operatorname{Diag}_{\text{el}} \mathcal N = \qty{\varphi(n_1, \dots n_k) \mid \varphi \text{ is an } \mathcal L_{\mathcal N} \text{-formula}, \mathcal N \vDash \varphi(n_1, \dots, n_k)} \]
\end{definition}
The diagram of a group is a slight generalisation of its multiplication table.
Note that a model of a diagram is the same as an extension, and a model of an elementary diagram is the same as an elementary extension.
\begin{lemma}
    Let \( \mathcal T \) be a consistent theory, and let \( \mathcal T_\forall \) be the theory of universal sentences proven by \( \mathcal T \).
    If \( \mathcal N \) is a model of \( \mathcal T_\forall \), then \( \mathcal T \cup \operatorname{Diag} {\mathcal N} \) is consistent.
\end{lemma}
\begin{proof}
    Suppose \( \mathcal T \cup \operatorname{Diag} {\mathcal N} \) is inconsistent.
    As \( \mathcal T \) is consistent, by compactness there must be a finite number of sentences in the diagram \( \operatorname{Diag} {\mathcal N} \) that are inconsistent with \( \mathcal T \).
    Taking the conjunction, we can reduce to the case where there is a single sentence \( \varphi(\vb n) \) that is inconsistent with \( \mathcal T \).
    Then as \( \mathcal T \cup \qty{\varphi(\vb n)} \) is inconsistent, \( \mathcal T \vdash \neg\varphi(\vb n) \).
    Since \( \mathcal T \) has nothing to say about the new constants \( \vb n \), we must in fact have \( \mathcal T \vdash \forall \vb x.\, \neg \varphi(\vb x) \).
    This is a universal consequence of \( \mathcal T \), so by assumption \( \mathcal N \) models it, giving a contradiction.
\end{proof}
\begin{corollary}[Tarski, \L{}o\'s]
    An \( \mathcal L \)-theory \( \mathcal T \) has a universal axiomatisation if and only if it is preserved under substructures.
    That is, if \( \mathcal M \subseteq \mathcal N \) are substructures and \( \mathcal M \vDash \mathcal T \) then \( \mathcal N \vDash \mathcal T \).
    Dually, a theory has an existential axiomatisation if and only if it is preserved under extensions.
\end{corollary}
\begin{proof}
    One direction is clear.
    Suppose \( \mathcal T \) is preserved under taking substructures.
    If \( \mathcal N \vDash \mathcal T \), then \( \mathcal N \vDash \mathcal T_\forall \); we show that the converse also holds.
    By the previous proposition, \( \mathcal T \cup \operatorname{Diag} \mathcal N \) is consistent.
    Let \( \mathcal N^\star \) be a model of this theory.
    So \( \mathcal N^\star \) is an extension of \( \mathcal N \), and also models \( \mathcal T \).
    But as \( \mathcal T \) is preserved under substructures, \( \mathcal N \) must model \( \mathcal T \).
\end{proof}
We can show much more with the same method.
\begin{theorem}[elementary amalgamation theorem]
    Let \( \mathcal M, \mathcal N \) be \( \mathcal L \)-structures, and \( \vb m \in \mathcal M, \vb n \in \mathcal N \) be tuples of the same size such that \( (\mathcal M, \vb m) \equiv (\mathcal N, \vb n) \).
    Then there is an elementary extension \( \mathcal K \) of \( \mathcal M \) and an elementary embedding \( g : \mathcal N \rightarrowtail \mathcal K \) mapping each \( n_i \) to \( m_i \).
\end{theorem}
\begin{proof}
    Replacing \( \mathcal N \) with an isomorphic copy if required, we can assume \( \vb m = \vb n \), and that \( \mathcal M \) and \( \mathcal N \) have no other common elements.
    We show that the theory
    \[ \mathcal T = \operatorname{Diag}_{\text{el}} \mathcal M \cup \operatorname{Diag}_{\text{el}} \mathcal N \]
    is consistent, using compactness.
    Suppose that \( \Phi \) is a finite subset of sentences in \( \mathcal T \), which of course includes only finitely many sentences in \( \operatorname{Diag}_{\text{el}} \mathcal N \).
    Let the conjunction of those sentences be written as \( \varphi(\vb m, \vb k) \), where \( \varphi(\vb x, \vb y) \) is an \( \mathcal L_{\mathcal N} \)-formula, and \( \vb k \) are pairwise distinct elements of \( \mathcal N \setminus \vb m \).
    If \( \Phi \) is inconsistent, then
    \[ \operatorname{Diag}_{\text{el}} \mathcal M \vdash \neg \varphi(\vb m, \vb k) \]
    Since the elements of \( \vb k \) are distinct and not in \( \mathcal M \), we in fact have
    \[ \operatorname{Diag}_{\text{el}} \mathcal M \vdash \forall \vb y.\, \neg \varphi(\vb m, \vb y) \]
    In particular,
    \[ (\mathcal M, \vb m) \vDash \forall \vb y.\, \neg \varphi(\vb m, \vb y) \]
    By hypothesis,
    \[ (\mathcal N, \vb n) \vDash \forall \vb y.\, \neg \varphi(\vb m, \vb y) \]
    This is a contradiction, as \( \varphi(\vb m, \vb k) \in \operatorname{Diag}_{\text{el}} \mathcal N \).
    Hence \( \mathcal T \) is consistent.
    Take \( \mathcal K \) to be the \( \mathcal L \)-reduct of a model of \( \mathcal T \).
\end{proof}
We can also use this technique to constrain the size of a model.
\begin{theorem}[L\"owenheim--Skolem theorem]
    Let \( \mathcal M \) be an infinite \( \mathcal L \)-structure.
    Let \( \kappa \geq \abs{\mathcal L} \) be an infinite cardinal.
    Then,
    \begin{enumerate}
        \item if \( \kappa < \abs{\mathcal M} \), there is an elementary substructure of \( \mathcal M \) of size \( \kappa \);
        \item if \( \kappa > \abs{\mathcal M} \), there is an elementary extension of \( \mathcal M \) of size \( \kappa \).
    \end{enumerate}
\end{theorem}
We postpone the proof of part (i).
\begin{proof}
    Expand the language \( \mathcal L \) by adding constant symbols for each \( m \in \mathcal M \) and \( c \in \kappa \).
    Let
    \[ \mathcal T = \operatorname{Diag}_{\text{el}} \mathcal M \cup \bigcup_{c \neq c' \in \kappa} \qty{\neg(c = c')} \]
    \( \mathcal T \) has a model by compactness, and this model must be an elementary extension of \( \mathcal M \) with size at least \( \kappa \).
    We then apply the downward L\"owenheim--Skolem theorem if necessary to obtain a model of size exactly \( \kappa \).
\end{proof}
For example, if \( \mathcal L \) is countable, every infinite \( \mathcal L \)-structure has a countable elementary substructure.
